from typing import List


class Solution:
    """
    贪心+动态规划
    因为每次只能往下或者往右走，则对于第一行每个数来说，走到它的最短路径和就是前一个数的和加上自己本身，即dp[0][j]+=dp[0][j-1]第一列同理
    而对于其他坐标的数来说，它的最短路径和就是左边或者上边的数的路径和加上自己，根据贪心算法，肯定要选这两个数中较小的路径和，状态方程为：
    dp[i][j] += min(dp[i-1][j], dp[i][j-1])
    """

    @classmethod
    def min_path_sum(cls, grid: List[List[int]]):
        dp = grid
        row, column = len(grid), len(grid[0])
        # 第一列所有的坐标数的路径和
        for i in range(1, row):
            dp[i][0] += dp[i - 1][0]
        # 第一行所有的坐标数的路径和
        for j in range(1, column):
            dp[0][j] += dp[0][j - 1]
        # 计算从[1,1]开始的每个数的路径和，根据贪心找到左边和上边两个数之间最小的数
        for i in range(1, row):
            for j in range(1, column):
                dp[i][j] += min(dp[i - 1][j], dp[i][j - 1])

        return dp[row - 1][column - 1]


if __name__ == '__main__':
    print(Solution.min_path_sum([[1, 3, 1], [1, 5, 1], [4, 2, 1]]))
    print(Solution.min_path_sum([[1, 2, 3], [4, 5, 6]]))
